package com.zk.algorithm.array;

import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.PriorityQueue;
import java.util.Queue;

@LeetCodeExplore
@Hard
public class FindMedianFromDataStream {

    private Queue<Integer> small = new PriorityQueue<Integer>((a,b) -> a.compareTo(b));
    private Queue<Integer> large = new PriorityQueue<Integer>((a,b) -> b.compareTo(a));

    // 核心思想就是：
    // - 每多一个数字，进一下大堆，然后从大堆中把最大的值放到小堆中
    // - 每多一个数字，进一下小堆，然后从小堆中把最小的值放到大堆中
    //
    // - 你给我一个，我给你一个，你给我一个，我给你一个
    //
    // - 最终，每个元素都经历了大堆和小堆
    public void addNum(int num) {
        large.add(num);
        small.add(large.poll());

        if (large.size() < small.size())
            large.add(small.poll());
    }

    public double findMedian() {
        return large.size() > small.size()
                ? large.peek()
                : (large.peek() / 2.0 + small.peek() / 2.0) /** 避免溢出 **/;
    }

}